package com.wrial.offer;
/*
 * @Author  Wrial
 * @Date Created in 22:18 2020/4/1
 * @Description 二叉树的最近公共祖先
 */

public class FaceTest_68_II {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果不是p或者是q的话，从下往上递归都为空
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 因为不在左分支就说明在右分支
        if (left == null) return right;
        if (right ==null) return left;
        // 如果左右都有的话就返回root
        return root;


    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
